package 链表

/*
https://leetcode.cn/problems/add-two-numbers/solutions/435246/liang-shu-xiang-jia-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked

2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
*/

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	dummyNode := &ListNode{0, nil} // 创建一个哑元节点，它的指针指向新链表的头节点
	preNode := dummyNode           // preNode表示当前节点的前一个节点
	carry := 0                     // 表示两个节点相加进位的值

	for l1 != nil || l2 != nil || carry != 0 { // 两个链表只要有一个不为空，或者有进位就一直循环
		sum := carry   // 当前节点的累加值，需要加上前面进位的值
		if l1 != nil { // 如果第一个链表的当前节点不为空，加上第一个链表当前节点的值
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil { // 第二个链表，同上
			sum += l2.Val
			l2 = l2.Next
		}

		// 创建新链表，preNode的next指针指向新的链表
		// 因为链表节点只能存储一位数字，所以这里要对sum求余，取个位数
		newNode := &ListNode{sum % 10, nil}
		preNode.Next = newNode

		carry = sum / 10 // 更新carry的值
		preNode = newNode
	}

	return dummyNode.Next // 返回哑元节点的下一个节点，它是新链表的头节点
}
